package com.alex.algorithm.easy;

import java.util.HashMap;
import java.util.Map;

/**
 * @lc app=leetcode id=1 lang=java
 *
 * [1] Two Sum
 *
 * https://leetcode.com/problems/two-sum/description/
 *
 * algorithms
 * Easy (42.04%)
 * Total Accepted:    1.5M
 * Total Submissions: 3.6M
 * Testcase Example:  '[2,7,11,15]\n9'
 *
 * Given an array of integers, return indices of the two numbers such that they
 * add up to a specific target.
 *
 * You may assume that each input would have exactly one solution, and you may
 * not use the same element twice.
 *
 * Example:
 *
 *
 * Given nums = [2, 7, 11, 15], target = 9,
 *
 * Because nums[0] + nums[1] = 2 + 7 = 9,
 * return [0, 1].
 *
 *
 *
 *
 */
public class Twosum {

    public static void main(String[] args) {
        int[] array = twoSum(new int[]{3,2,4,5,1,6,7}, 10);
        System.out.println(array[0] + "," + array[1]);
    }

    public static int[] twoSum(int[] nums, int target) {
        int[] indexArray = new int[2];

        Map<Integer, Integer> valIndexMap = new HashMap<>();
        for(int i = 0; i < nums.length; ++i) {
            valIndexMap.put(nums[i], i);
        }
        for(int j = 0; j < nums.length; ++j) {
            int gap = target - nums[j];
            Integer index = valIndexMap.get(gap);
            if(index != null && j != index) {
                indexArray[0] = j;
                indexArray[1] = index;
                break;
            }
        }

        return indexArray;
    }
}
